# -*-* encoding:UTF-8 -*-
# author            : mengy
# date              : 2019/1/3
# python-version    : Python 3.7.0
# description       : 常见的排序
import time


class Sort:
    def bubble_sort(self, array):
        """
        冒泡排序 \n
        冒泡排序的思想:
            总是把最大的元素放在数组的末尾，因此第一趟排序后，最大的元素一定在数组最后，然后对剩下的n-1个元素进行同样的排序（贪心算法） \n
        冒泡排序是稳定的排序算法 \n
        时间复杂度:O(n^2) \n
        :return:
        """
        if len(array) <= 0:
            raise Exception('待排序的数组为空')
        try:
            for i in range(1, len(array)):
                for j in range(len(array) - i):
                    if array[j] > array[j + 1]:
                        tmp = array[j]
                        array[j] = array[j + 1]
                        array[j + 1] = tmp
        except Exception as e:
            print("冒泡排序发生异常，原因:" + e)
        finally:
            return array

    def insert_sort(self, array):
        """
        直接插入排序 \n
        直接插入排序的思想: \n
            将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过。\n
        直接插入排序是稳定的排序 \n
        时间复杂度:O(n^2)
        :param array:
        :return:
        """
        if len(array) <= 0:
            raise Exception('待排序的数组为空')
        try:
            for i in range(1, len(array)):
                for j in range(i - 1, -1, -1):
                    if array[j] > array[j + 1]:
                        tmp = array[j]
                        array[j] = array[j + 1]
                        array[j + 1] = tmp
        except Exception as e:
            print("插入排序发生异常，原因:" + e)
        finally:
            return array

    def shell_sort(self, array):
        """
        希尔排序 \n
        希尔排序的算法思想： \n
            将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将gap折半减小，循环上述操作；\n
            当gap=1时，利用直接插入，完成排序。\n
        希尔排序是不稳定的排序 \n
        时间复杂度:O(n^1.3)
        :return:
        """
        if len(array) <= 0:
            raise Exception('待排序的数组为空')
        try:
            step = int(len(array) / 2)
            while step >= 1:
                for i in range(step, len(array)):
                    for j in range(i - step, -1, -step):
                        if array[j] > array[j + step]:
                            tmp = array[j]
                            array[j] = array[j + step]
                            array[j + step] = tmp
                step = int(step / 2)
        except Exception as e:
            print("希尔排序发生异常，原因:" + e)
        finally:
            return array

    def select_sort(self, array):
        """
        选择排序 \n
        选择排序的基本思想：比较+交换。\n
            · 从待排序序列中，找到关键字最小的元素；\n
            · 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；\n
            · 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。\n
        选择排序是不稳定的排序 \n
        时间复杂度:O(n^2)
        :param array:
        :return:
        """
        if len(array) <= 0:
            raise Exception('待排序的数组为空')
        try:
            for i in range(0, len(array)):
                minimum = array[i]
                for j in range(i + 1, len(array)):
                    if array[j] < minimum:
                        tmp = array[j]
                        array[j] = minimum
                        minimum = tmp
                array[i] = minimum
        except Exception as e:
            print("选择排序发生异常，原因:" + e)
        finally:
            return array


    def heap_sort(self, array):
        """
        堆排序 \n
        堆排序的基本思想：
            本质是一种数组对象。特别重要的一点性质：任意的叶子节点小于（或大于）它所有的父节点。
            对此，又分为大顶堆和小顶堆，大顶堆要求节点的元素都要大于其孩子，小顶堆要求节点元素都小于其左右孩子，
            两者对左右孩子的大小关系不做任何要求。利用堆排序，就是基于大顶堆或者小顶堆的一种排序方法
        堆排序是不稳定的排序 \n
        时间复杂度:O(n^2)
        :param array:
        :return:
        """
        if len(array) <= 0:
            raise Exception('待排序的数组为空')
        try:
            for i in range(0, len(array)):
              pass
        except Exception as e:
            print("选择排序发生异常，原因:" + e)
        finally:
            return array


if __name__ == '__main__':
    array = [5, 4, 6, 8, 9, 2, 7, 3, 1, 10, 15, 16, 13, 11, 12, 18, 19, 31, 21, 20, 26, 35, 15, 65, 59, 48, 57, 68, 16]
    sort = Sort()
    print(array)
    # start1 = time.time()
    # sorted1 = sort.bubble_sort(array)
    # end1 = time.time()
    # print(sorted1)
    # print("共耗时 %d us" % (end1 * 1000000 - start1 * 1000000))
    # start2 = time.time()
    # sorted2 = sort.insert_sort(array)
    # end2 = time.time()
    # print(sorted2)
    # print("共耗时 %d us" % (end2 * 1000000 - start2 * 1000000))
    # start3 = time.time()
    # sorted3 = sort.shell_sort(array)
    # end3 = time.time()
    # print(sorted3)
    # print("共耗时 %d us" % (end3 * 1000000 - start3 * 1000000))
    start4 = time.time()
    sorted4 = sort.select_sort(array)
    end4 = time.time()
    print(sorted4)
    print("共耗时 %d us" % (end4 * 1000000 - start4 * 1000000))
